package com.atguigu.tree;


import lombok.Getter;
import lombok.Setter;

import javax.swing.tree.TreeNode;

/**
 * @Author : 孙峰
 * @Description:
 * @Date : 2021/10/4  22:05
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 首先创建一个二叉树
        HeroNode root = new HeroNode(1, "松江");
        HeroNode heroNode2 = new HeroNode(2, "吴用");

        HeroNode heroNode3 = new HeroNode(3, "卢俊义");
        HeroNode heroNode4 = new HeroNode(4, "林冲");
        HeroNode heroNode5 = new HeroNode(5, "关胜");
        // 说明 我们先手动创建二叉树

        root.setLeft(heroNode2);
        root.setRight(heroNode3);
        heroNode3.setRight(heroNode4);
        heroNode3.setLeft(heroNode5);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(root);
//        binaryTree.preOder(); //1 2 3 5 4
        //       binaryTree.inOder(); // 2 1 5 3 4
        //    binaryTree.postOder(); //   2 5 4 3 1
        // 前序查找
        HeroNode preOderSearch = binaryTree.preOderSearch(5);
        System.out.println(preOderSearch);
        // 中序查找
        HeroNode inOderSearch = binaryTree.inOderSearch(15);
        System.out.println(inOderSearch);
        // 后序查找
        HeroNode postOderSearch = binaryTree.postOderSearch(5);
        System.out.println(postOderSearch);
    }
}


class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    // 删除节点
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("这是一个空树，不能进行删除");
        }
    }

    public void preOder() {
        if (this.root != null) {
            this.root.preOrderTraverse();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void inOder() {
        if (this.root != null) {
            this.root.inOrderTraverse();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void postOder() {
        if (this.root != null) {
            this.root.postOrderTraverse();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public HeroNode preOderSearch(int no) {
        if (root != null) {
            return root.preOderSearch(no);
        } else {
            return null;
        }
    }

    public HeroNode inOderSearch(int no) {
        if (root != null) {
            return root.inOderSearch(no);
        } else {
            return null;
        }
    }

    public HeroNode postOderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

// 先创建节点
@Getter
@Setter
class HeroNode//节点结构
{
    private int no;

    private String name;
    private HeroNode left; // 默认null
    private HeroNode right; // 默认null

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }


    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    // 前序遍历的方法   前序遍历的输出方式   首先输出当前节点
    public void preOrderTraverse() {
        // 先输出当前节点
        System.out.println(this);
        //递归向左子树遍历
        if (this.left != null) {
            this.left.preOrderTraverse();
        }

        //递归向右子树遍历
        if (this.right != null) {
            this.right.preOrderTraverse();
        }
    }

    public void inOrderTraverse() {
        //递归向左子树遍历
        if (this.left != null) {
            this.left.inOrderTraverse();
        }
        // 先输出当前节点
        System.out.println(this);
        //递归向右子树遍历
        if (this.right != null) {
            this.right.inOrderTraverse();
        }
    }

    public void postOrderTraverse() {
        //递归向左子树遍历
        if (this.left != null) {
            this.left.postOrderTraverse();
        }
        //递归向右子树遍历
        if (this.right != null) {
            this.right.postOrderTraverse();
        }
        // 先输出当前节点
        System.out.println(this);

    }

    public HeroNode preOderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        // 向左递归
        if (this.left != null) {
            resNode = this.left.preOderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        // 向右递归
        if (this.right != null) {
            resNode = this.right.preOderSearch(no);
        }
        return resNode;
    }

    public HeroNode inOderSearch(int no) {

        HeroNode resNode = null;
        // 向左递归
        if (this.left != null) {
            resNode = this.left.inOderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.no == no) {
            return this;
        }

        // 向右递归
        if (this.right != null) {
            resNode = this.right.inOderSearch(no);
        }
        return resNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        // 向左递归
        if (this.left != null) {
            resNode = this.left.inOderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        // 向右递归
        if (this.right != null) {
            resNode = this.right.inOderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        return null;
    }

    public void delNode(int no) {
        // 判断左子树是否存在，并且判断左子树是否为要删除的节点  如果山则进行删除
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        // 判断右子树是否存在，并且判断右子树是否为要删除的节点  如果山则进行删除
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        // 如果以上没有删除成功,则左子树递归删除
        if (this.left != null) {
            this.left.delNode(no);
        }
        // 如果左子树没有删除成功,则右子树递归删除
        if (this.right != null) {
            this.right.delNode(no);
        }


    }

}